#include <iostream>
#include <vector>

using namespace std;

class Sort
{
public:
	void Print(vector<int>& nums)
	{
		for (auto& e : nums)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void  InsertSort(vector<int>& nums)
	{
		for (int i = 0; i < nums.size() - 1; i++)
		{
			for (int j = i + 1; j > 0 && nums[j - 1] > nums[j]; j--)
			{
				swap(nums[j], nums[j - 1]);
			}
		}
	}

	void ShellSort(vector<int>& nums, int n) // ？
	{
		int gap = n;
		while (gap > 1)
		{
			gap = gap / 3 + 1;
			for (int i = 0; i < nums.size() - gap; i++)
			{
				int j = 0;
				for (int j = gap; j > 0 && nums[j - gap] > nums[j]; j -= gap)
				{
					swap(nums[j], nums[j - gap]);
				}
			}
		}

	}

	void BubbleSort(vector<int>& nums)
	{
		bool flag = false;
		for (int i = 0; i < nums.size() - 1; i++)
		{
			for (int j = 1; j < nums.size() - i; j++)
			{
				if (nums[j - 1] > nums[j])
				{
					swap(nums[j - 1], nums[j]);
					flag = true;
				}
			}
			if (!flag) break;
		}
	}
};

int main()
{
	vector<int> v = { 1,9,7,3,8,2,5,4,6 };
	Sort sort;
	//sort.BubbleSort(v);
	sort.InsertSort(v);
	//sort.ShellSort(v, 3);
	sort.Print(v);
	return 0;
}